Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

  1. Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
  3. Return:
  4. ["AAAAACCCCC", "CCCCCAAAAA"].

Solution:

  1. public class Solution {
  2.   public List<String> findRepeatedDnaSequences(String s) {
  3.     int len = s.length();
  5.     if (len < 10) {
  6.       return new LinkedList<String>();
  7.     }
  9.     int a = 0;
  10.     int m = 1;
  12.     for (int i = 0; i < 10; i++) {
  13.       a = a * 4 + getCode(s.charAt(i));
  14.       m *= 4;
  15.     }
  17.     HashSet<Integer> set = new HashSet<Integer>();
  18.     HashSet<Integer> r = new HashSet<Integer>();
  19.     LinkedList<String> result = new LinkedList<String>();
  21.     set.add(a);
  23.     int p = 10;
  25.     while (p < len) {
  26.       a = (a * 4 + getCode(s.charAt(p))) % m;
  28.       if (set.contains(a) && !r.contains(a)) {
  29.         result.add(s.substring(p - 9, p + 1));
  30.         r.add(a);
  31.       }
  32.       else {
  33.         set.add(a);
  34.       }
  36.       p++;
  37.     }
  39.     return result;
  40.   }
  42.   private int getCode(char c) {
  43.     if (c == 'C') return 1;
  44.     if (c == 'G') return 2;
  45.     if (c == 'T') return 3;
  46.     return 0;
  47.   }
  48. }